class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

class Solution: # 快慢指针法，如果有环，则快指针会追上慢指针，否则不会相遇，空间复杂度为O(1)
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
# class Solution: 方法二（哈希表），空间复杂度为O(n)
#     def hasCycle(self, head):
#         set_map = set()
#         curr = head
#         while curr:
#             if curr in set_map:
#                 return True
#             set_map.add(curr)
#             curr = curr.next
#         return False

# 构建链表并制造环
def createLinkedListWithCycle(values, pos):
    """
    values: 节点的值列表
    pos: 指定尾节点连接的位置，-1表示无环
    """
    if not values:
        return None

    dummy = ListNode(0)
    curr = dummy
    cycle_node = None

    for idx, val in enumerate(values):
        curr.next = ListNode(val)
        curr = curr.next
        if idx == pos:
            cycle_node = curr

    if pos != -1:
        curr.next = cycle_node

    return dummy.next

if __name__ == '__main__':
    # 示例：head = [3, 2, 0, -4], pos = 1
    values = [3, 2, 0, -4]
    pos = 1  # 表示尾节点指向第2个节点（索引1）

    head = createLinkedListWithCycle(values, pos)

    s = Solution()
    res = s.hasCycle(head)
    print(res)  # 输出 True
